package a00_LeetCode.Tree;

/**
 * @Author quan
 * @Description 最近公共祖先问题！！！看不懂
 * @Date 2023/3/29 11:20
 */
public class Num236_LCA {
    TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        findFun(root,p,q);
        return lca;
    }
    //在当前以root为根的二叉树中，能否找到p或者q
    private boolean findFun(TreeNode root, TreeNode p, TreeNode q) {
        //base case
        if(root == null){
            return false;
        }
        //先在左子树中找p或者q
        int left = findFun(root.left,p,q) ? 1:0;
        //在右子树中找p或者q
        int right = findFun(root.right,p,q) ? 1: 0;
        //在根节点找p或者q
        int mid = (root == p || root == q)? 1: 0;
        //如果在这三个位置上有两个位置上都找到了，说明该根节点为最近公共祖先
        if(left + mid + right == 2){
            lca = root;
        }
        return left + right + mid > 0 ;
    }
}
